class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();

        vector<vector<int>> dp(n, vector<int>(2));

        // dp[i][0]: 第i天结束时未持有股票
        // dp[i][1]: 第i天结束时持有股票

        // i这一天的开始就是i - 1天的结束，这句话很重要
        // 第i天结束时未持有股票，有两种状态可以到达
        // 1. i - 1天到i这一天结束时啥也不干，也就是i这一天开始就是没有股票的，i这一天结束也没有股票，dp[i - 1][0];
        // 2. i这一天开始是持有股票的，i天结束后把它卖了，dp[i - 1][1] + prices[i];

        // 同理，第i天结束时持有股票，也有两种状态可以达到
        // 1. i天开始就持有股票，并且这一天啥也不干，那么就是dp[i - 1][1];
        // 2. i这一天开始是没有股票的，i天结束后买了股票，就是dp[i - 1][0] - prices[i];

        // 初始化
        // 第0天结束时我未持有股票，说明我这一天结束时啥也没干，利润还是0
        dp[0][0] = 0;

        // 第0天结束时我持有股票，说明这一天我就把股票买了
        dp[0][1] = -prices[0] - fee;

        // 填表
        for(int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] );
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
        }

        return dp[n - 1][0];
    }
};